package tsp;


import java.util.*;

/**
 * Created by v on 17-6-7.
 */
public class Tsp {
    private static class Node {
        //还没有去的结点
        List<Integer> list;
        //是否已经完成了
        boolean solution;
        //出发结点
        int begin;
        //已经消耗的权值
        int bound;

        public Node(List<Integer> list, boolean solution, int begin, int bound) {
            this.list = list;
            this.solution = solution;
            this.begin = begin;
            this.bound = bound;
        }
    }

    //优先队列
    private static Queue<Node> queue = new PriorityQueue<>(((o1, o2) -> ((Integer) o1.bound).compareTo(o2.bound)));

    //最大值，相当于无穷大
    private static final int MAX = Integer.MAX_VALUE / 2;

    //原始矩阵
    private static int[][] matrix;

    //主要驱动函数
    private static int solve() {
        List<Integer> list = new LinkedList<>();
        for (int i = 1; i < matrix.length; i++) {
            list.add(i);
        }
        Node node = new Node(list, false, 0, 0);
        queue.offer(node);

        while (!queue.isEmpty()) {
            node = queue.poll();
            //如果队列弹出了一个已经到达终点的节点，那么它的耗费就是最大耗费了。
            if (node.solution) {
                return node.bound;
            }

            list = node.list;
            //如果已经走完所有的点了，则加上回去0号点的耗费，再次载入到优先队列
            if (list.size() == 0) {
                node.bound = node.bound + matrix[node.begin][0];
                node.solution = true;
                queue.offer(node);
                continue;
            }

            //对于没有走完的节点，对每个节点创建一个新的孩子节点并放入优先队列
            for (int end : list) {
                List<Integer> list1 = clone(list, end);
                int bound = node.bound + matrix[node.begin][end];
                Node node1 = new Node(list1, false, end, bound);
                queue.offer(node1);
            }
        }

        return -1;
    }

    private static List<Integer> clone(List<Integer> list, int current) {
        List list1 = new LinkedList();
        for (int i = 0; i < list.size(); i++) {
            if (list.get(i) != current) {
                list1.add(list.get(i));
            }
        }

        return list1;
    }

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);

        System.out.println("请输入矩阵大小n:");

        int n = input.nextInt();
        System.out.println("请输入商旅问题的原始矩阵，在无穷大的地方输入-1:");
        matrix = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                matrix[i][j] = input.nextInt();

                if (matrix[i][j] == -1) {
                    matrix[i][j] = MAX;
                }
            }
        }

        for (int i = 0; i < n; i++) {
            matrix[i][i] = MAX;
        }

        System.out.println("所消耗的bound为：" + solve());
    }
}
